(use ['clojure.string :only ['join]])

(defn printboard [board]
  (println (join "\n" (map #(join (assoc (vec (repeat (count board) ".")) % "Q"))
			   board))))

(defn attacks
  "Check if queen on row q attacks queen on row r on board."
  [board q r]
  (let [qc (nth board q) rc (nth board r)]
    (or (== q r) (== qc rc) (== qc (+ rc (- r q))) (== qc (- rc (- r q))))))

(defn checkboard
  "Check that all queens on board up to row don't attack queen on row."
  [board row]
  (not (some #(attacks board row %) (range row))))

(defn queens [n]
  "Find all solutions to the N-queens problem."
  (letfn [(bump [board row] (assoc board row (inc (nth board row))))]
    (loop [board (assoc (vec (repeat n -1)) 0 0)
	   row 0
	   result []]
      (cond (== (nth board row) n)
	    (if (== row 0) result
		(recur (bump (assoc board row -1) (dec row)) (dec row) result))
	    (not (checkboard board row)) (recur (bump board row) row result)
	    (== row (dec n)) (recur (bump board row) row (conj result board))
	    :else (recur (bump board (inc row)) (inc row) result)))))
	  
(defn find-boards
  "Find all solutions for the N-queens problem starting with board up to row."
  [board row]
  (let [cols (count board)
	nr (inc row)
	nbs (filter #(checkboard % row) (map #(assoc board row %) (range cols)))]
    (if (== nr cols) nbs (mapcat #(find-boards % nr) nbs))))

(defn recursive-queens
  "Recursively find solutions for the N-queens problem."
  [n]
  (find-boards (vec (repeat n -1)) 0))

(defn find-boards-threading
  "Start threads to find solutions for the N-queens problem from our starting point."
  [board row]
  (let [cols (count board)
	nr (inc row)
	nbs (filter #(checkboard % row) (map #(assoc board row %) (range cols)))]
    (if (== nr cols) nbs (apply concat (pmap #(find-boards-threading % nr) nbs)))))

(defn threaded-queens
  "Find solutions to the N-queens problem in parallel."
  [n]
  (find-boards-threading (vec (repeat n -1)) 0))

(defn find-boards-threading-1
  "Start threads to find solutions for the N-queens problem from our starting point."
  [board row]
  (let [cols (count board)
	nr (inc row)
	nbs (filter #(checkboard % row) (map #(assoc board row %) (range cols)))]
    (if (== nr cols) nbs (apply concat (pmap #(find-boards % nr) nbs)))))

(defn threaded-queens-1
  "Find solutions to the N-queens problem in parallel."
  [n]
  (find-boards-threading-1 (vec (repeat n -1)) 0))

(defn find-boards-threading-n
  "Start threads to find solutions for the N-queens problem from our starting point."
  [board row]
  (let [cols (count board)
	nr (inc row)
	nbs (filter #(checkboard % row) (map #(assoc board row %) (range cols)))
	finder (if (< (count nbs) 8) find-boards find-boards-threading-n)]
    (if (== nr cols) nbs (apply concat (pmap #(finder % nr) nbs)))))

(defn threaded-queens-n
  "Find solutions to the N-queens problem in parallel."
  [n]
  (find-boards-threading-n (vec (repeat n -1)) 0))

